#include <vector>

class MaxHeap {
private:
    std::vector<int> heap;

    int parent(int index) {
        return (index - 1) / 2;
    }

    int leftChild(int index) {
        return 2 * index + 1;
    }

    int rightChild(int index) {
        return 2 * index + 2;
    }

    void swap(int& a, int& b) {
        int temp = a;
        a = b;
        b = temp;
    }

    void siftUp(int index) {
        while (index > 0 && heap[index] > heap[parent(index)]) {
            swap(heap[index], heap[parent(index)]);
            index = parent(index);
        }
    }

    void siftDown(int index) {
        int maxIndex = index;
        int leftIndex = leftChild(index);
        int rightIndex = rightChild(index);

        if (leftIndex < heap.size() && heap[leftIndex] > heap[maxIndex]) {
            maxIndex = leftIndex;
        }

        if (rightIndex < heap.size() && heap[rightIndex] > heap[maxIndex]) {
            maxIndex = rightIndex;
        }

        if (index != maxIndex) {
            swap(heap[index], heap[maxIndex]);
            siftDown(maxIndex);
        }
    }

public:
    void insert(int value) {
        heap.push_back(value);
        siftUp(heap.size() - 1);
    }

    int extractMax() {
        if (heap.empty()) {
            return -1; // or any other appropriate handling for an empty heap
        }

        int max = heap[0];
        swap(heap[0], heap[heap.size() - 1]);
        heap.pop_back();
        siftDown(0);

        return max;
    }
};
#include <iostream>

int main() {
    MaxHeap heap;

    heap.insert(10);
    heap.insert(5);
    heap.insert(20);
    heap.insert(3);

    int max_value = heap.extractMax();
    std::cout << max_value << std::endl;  // 输出：20

    return 0;
}